#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>

using namespace std;
using LL = long long;
const int N = 7e5 + 10;
/*
本题关键点
当i对j说imposter时， i和j是异类
当i对j说crewmate时，i和j是同类

通过建图:我们将类型不同的两个人连一条边，类型相同的两个人则通过一个fake node 进行连边（x-fake node- y）。
可以维护图中任意相邻的两个点的值相反的特性

然后通过给每个连通块赋值来求出max值

*/

int n, m;
vector<int> v[N * 2];
int cnt[2];
int col[N * 2];
int idx;
bool ok;

void dfs(int u){
    for(int k : v[u]){
        if(col[u] == col[k]){
            ok = false;
            return;
        }
        if(col[k] != - 1) continue;

        col[k] = 1 - col[u];
        if(k <= n) cnt[col[k]] ++;
        dfs(k);
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 0; i <= n + m; i ++){
        v[i].clear();
        col[i] = -1;
    }
    cnt[0] = cnt[1] = 0;
    ok = true;
    idx = n;


    for(int i = 1; i <= m; i ++){
        int x, y;
        string c;
        cin >> x >> y >> c;

        if(c == "imposter"){
            v[x].push_back(y);
            v[y].push_back(x);
        }else{
            v[x].push_back(++idx);
            v[y].push_back(idx);
            v[idx].push_back(x);
            v[idx].push_back(y);
        }
    }
    int res = 0;

    for(int i = 1; i <= n; i ++){
        if(col[i] != - 1) continue;

        col[i] = 1;
        cnt[1] = 1, cnt[0] = 0;
        dfs(i);

        if(!ok){
            cout << -1 << '\n';
            return;
        }

        res += max(cnt[0], cnt[1]);
    }

    cout << res << '\n';


}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        solve();
    }


    return 0;
}